The present invention relates to computer processors, and more particularly, to branch predictors for computer processors.
In computer architecture, a branch predictor is a digital circuit that attempts to determine which direction a conditional branch may follow in an instruction stream. Branching is usually implemented with a conditional jump instruction, and once encountered, a branch may be “taken” or “not taken.” If taken, the instruction flow may continue in a first direction, and if “not taken,” the instruction flow may continue in a second direction. One example of a conditional branch is an “if-then-else” structure used in computer programming.
High-performance processors, which tend to be deeply pipelined, typically rely on branch predictors to continuously supply the core with instructions. Branch predictors essentially improve the flow of instructions in the pipeline to keep the pipeline full and maintain performance. Without branch prediction, the processor would have to wait until the conditional jump instruction has passed the execute stage before the next instruction could enter the pipeline. Branch predictors attempt to avoid this delay by predicting whether the conditional jump is most likely to be taken or not taken.
Research around a class of predictors referred to as neurally-inspired perceptron branch predictors has shown certain improvements in prediction accuracy by exploiting correlations in long branch histories. However, systems with moderate hardware budgets, such as on the order of 32 to 64 KB, typically restrict such predictors from correlating beyond 32 to 64 branches in a dynamic execution stream. As some correlations may only become evident over larger distances, such as on the order of 512 to 1024 branches apart, such predictors are consequently limited in their prediction ability.
Some attempts at correlating branches over larger distances have included increasing the branch prediction hardware budget, such as to 1 MB, in an effort to track more branches. However, such larger data structures undesirably result in increased access latencies and increased power consumption. Also, such larger data structures undesirably cause increased training times for the neural-based perceptron predictors.
A need therefore exists to provide a branch predictor with increased performance that eliminates one or more of the foregoing disadvantages.